/*
 * Copyright (C) 2007 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.android.dx.util;

import java.util.Arrays;

/**
 * A list of labeled items, allowing easy lookup by label.
 */
public class LabeledList extends FixedSizeList {

	/**
	 * Sparse array indexed by label to FixedSizeList index; {@code -1} for an
	 * invalid label.
	 */
	private final IntList labelToIndex;

	/** @inheritDoc */
	public LabeledList(int size) {
		super(size);

		labelToIndex = new IntList(size);
	}

	/**
	 * Constructs a new instance that is a copy of the old instance.
	 * 
	 * @param old
	 *            instance to copy
	 */
	public LabeledList(LabeledList old) {
		super(old.size());
		labelToIndex = old.labelToIndex.mutableCopy();

		int sz = old.size();

		for (int i = 0; i < sz; i++) {
			Object one = old.get0(i);
			if (one != null) {
				set0(i, one);
			}
		}
	}

	/**
	 * Gets the maximum label (exclusive) of any block added to this instance.
	 * 
	 * @return {@code >= 0;} the maximum label
	 */
	public final int getMaxLabel() {
		int sz = labelToIndex.size();

		// Gobble any deleted labels that may be at the end.
		int i;
		for (i = sz - 1; (i >= 0) && (labelToIndex.get(i) < 0); i--)
			/* empty */;

		int newSize = i + 1;

		labelToIndex.shrink(newSize);

		return newSize;
	}

	/**
	 * Removes a label from the label-to-index mapping.
	 * 
	 * @param oldLabel
	 *            label to remove
	 */
	private void removeLabel(int oldLabel) {
		labelToIndex.set(oldLabel, -1);
	}

	/**
	 * Adds a label and index to the label-to-index mapping.
	 * 
	 * @param label
	 *            new label
	 * @param index
	 *            index of block.
	 */
	private void addLabelIndex(int label, int index) {
		int origSz = labelToIndex.size();

		for (int i = 0; i <= (label - origSz); i++) {
			labelToIndex.add(-1);
		}

		labelToIndex.set(label, index);
	}

	/**
	 * Gets the index of the first item in the list with the given label, if
	 * any.
	 * 
	 * @param label
	 *            {@code >= 0;} the label to look for
	 * @return {@code >= -1;} the index of the so-labelled item, or {@code -1}
	 *         if none is found
	 */
	public final int indexOfLabel(int label) {
		if (label >= labelToIndex.size()) {
			return -1;
		} else {
			return labelToIndex.get(label);
		}
	}

	/**
	 * Gets an array containing all of the labels used in this instance, in
	 * order. The returned array is freshly-allocated and so may be modified
	 * safely by the caller without impacting this instance.
	 * 
	 * @return {@code non-null;} ordered array of labels
	 * @throws NullPointerException
	 *             thrown if there are any {@code null} items in this instance
	 */
	public final int[] getLabelsInOrder() {
		int sz = size();
		int[] result = new int[sz];

		for (int i = 0; i < sz; i++) {
			LabeledItem li = (LabeledItem) get0(i);
			if (li == null) {
				throw new NullPointerException("null at index " + i);
			}
			result[i] = li.getLabel();
		}

		Arrays.sort(result);
		return result;
	}

	/** @inheritDoc */
	@Override
	public void shrinkToFit() {
		super.shrinkToFit();

		rebuildLabelToIndex();
	}

	/**
	 * Rebuilds the label-to-index mapping after a {@code shrinkToFit()}. Note:
	 * This assumes that the labels that are in the list are the same, although
	 * the indicies may have changed.
	 */
	private void rebuildLabelToIndex() {
		int szItems = size();

		for (int i = 0; i < szItems; i++) {
			LabeledItem li = (LabeledItem) get0(i);

			if (li != null) {
				labelToIndex.set(li.getLabel(), i);
			}
		}
	}

	/**
	 * Sets the element at the given index.
	 * 
	 * @param n
	 *            {@code >= 0, < size();} which element
	 * @param item
	 *            {@code null-ok;} the value to store
	 */
	protected void set(int n, LabeledItem item) {
		LabeledItem old = (LabeledItem) getOrNull0(n);

		set0(n, item);

		if (old != null) {
			removeLabel(old.getLabel());
		}

		if (item != null) {
			addLabelIndex(item.getLabel(), n);
		}
	}
}
